﻿/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;

Node* aplyByNode(int x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->val = x;
    newnode->next = NULL;
    newnode->random = NULL;
    return newnode;
}

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    Node* pcur = head;
    Node* next = head->next;
    while (pcur) {
        Node* copy = aplyByNode(pcur->val);
        copy->next = next;
        pcur->next = copy;
        pcur = next;
        if (next) {
            next = next->next;
        }
    }
    Node* prev = head;
    pcur = prev->next;
    while (prev) {
        if (prev->random == NULL) {
            pcur->random = prev->random;
        }
        else {
            pcur->random = prev->random->next;
        }
        prev = pcur->next;
        if (prev) {
            pcur = prev->next;
        }
    }
    Node* newhead = head->next;
    pcur = head->next;
    prev = pcur->next;
    while (pcur->next) {
        pcur->next = prev->next;
        pcur = prev->next;
        prev = pcur->next;
    }
    return newhead;
}